	\chapter[js_sol]{Řešení problému Job-Shop}

Kapitola se bude zabývat návrhem modelu pro CSP a jeho implementací
(spojení s~knihovnou podporující CP Gecode a Matlabem).

\section{Model problému}
Prvním krokem k~využívání programování s~omezujícími podmínkami je návrh
modelu, který se pak předloží \quotation{řešiči}({\it constraint
		solveru}). Jeho výstupem je pak řešení modelu. Jedním
modelem se samozřejmě dá reprezentovat více problémů\footnote{Problémy
	nemusí být ani stejného (např. rozvrhovacího) charakteru.}
		
	\subsection{Reprezentace Job-shopu}
	
	Job-shop popsaný v~části \in[rozvrhovani-jobshop] je
	nejznámějším a nejužívanějším {\it shopem} z~uvedených v~části
	\in[rozvrhovani-shopy]. Přesto jsme chtěli, aby  se stejnými
	objekty dal namodelovat jak Job-shop, tak i Flow-shop resp. Open-shop. 
	
	Každá úloha v~jednotlivých jobech je vlastně proměnná
v~diskrétním čase; tím pádem se jednotlivé joby rozloží na jednu množinu úloh, mezi kterými existují precedenční vazby v~závislosti na daném
	problému.

	Pro úlohu jsme si vytvořili datovou strukturu, která sice obsahuje
	pouze zlomek vlastností, které byly jmenovány	 v~části
	\in[rozvrhovani-uloha], ale pro tento případ je dostačující.
	Úloha má vlastnosti:
		\startitemize
		\item Doba vykonávání $p_i$
		\item Stroj (dedicated processor) 
		\item Seznam úloh, které musí být provedené před jejím
		začátkem 
	\stopitemize	
	Vytvořili jsme seznam všech úloh, který slouží
k~zadání pro constraint solver. Každý prvek tohoto seznamu
	koresponduje s~jednou proměnnou CSP a má svoji doménu (tu maji
			ze začátku všechny úlohy stejnou) a precedenční
	vazby se také transformují na podmínky mezi proměnnými CSP.
	Navíc jsme vytvořili imaginární (\quotation{dummy}) úlohu, která
	značí konec celého rozvrhu a má v~seznamu předcházejících
	všechny úlohy.

	
	\subsection{Vstupní data}
	Vstup do programu jsme se snažili přizpůsobit standartnímu zápisu
	pomocí matic podle části \in[rozvrhovani-shopy]. 


\section{Hlavní algoritmus řešení}
Chování algoritmu je vidět z~vývojového diagramu na
obrázku \in[fig:flowchart]. Jednotlivé části bych rozvedl.
\startitemize
	\item Kontrola platnosti formátu dat: Vstupní data z~Matlabu se
	testují, zda mají formát podle vzorů v~maticích
	\in[eq:vstupjobShopu]. Navíc doby běhu musí být kladné a musí
	být zvolen druh problému (Flow-shop vs. Job-shop vs. Open-shop).
	Neprojde-li kontrolou, pak vypíše program chybové hlášení.
		\item Minimální čas rozvrhu: Zde je nutné uvést
	hlavní myšlenku algoritmu. V~začátcích naší práce jsme zkoumali,
	zda je výhodnější zvolit si čas, do
		kterého se rozvrh určitě vejde a hledat řešení v~čase o~jedna menším nebo vzít malou hodnotu času (určitě menší nebo rovnu optimálnímu času řešení) a hledat řešení pro daný časový interval, který se v~případě neúspěchu zvýší o~jednu časovou jednotku a hledá se až do okamžiku nalezení prvního řešení. V~obou případech máme zaručené optimální řešení (1. případ:pokud pro čas $T_d$ bylo řešení nalezeno a pro $T_d -1$ nebylo, pak $T_d$ je optimum; 2. případ: pokud pro čas $T_u$ nebylo nalezeno řešení a pro $T_u+1$ bylo hledání úspěšné, potom je rozvrh určitě optimální). Ukázalo se, že mnohem rychleji dojdeme k~řešení aplikováním druhého přístupu, přestože je první přístup obvyklejším. 

V~rovnici \in[eq:mintime] jsme si nadefinovali proměnnou minTime, která značí nejmenší čas, do kterého by bylo možné rozvrh naplánovat.
       \placeformula[eq:mintime]	
	\startformula \mbox{minTime}=\max \left\{
	\max_{i}{\displaystyle\sum_{j}T_{ij}}\mbox{, }
	\max_{k}{\displaystyle \sum _{\mu(T_{ij})=k} p(T_{ij})}
 \right\} 
			\stopformula

	\item Algoritmus: knihovna Gecode nabízí 3 prohledávací
	algoritmy, bohužel nejnadějnější z~nich LDS se nepodařilo
	rozběhnout. Chybu jsme zkoumali a nejspíše je uvnitř knihovny.
	
	BAB se v~našem přístupu k~řešení problému
	redukuje na prostý DFS, protože nedochází k~žádnému přidávání
	nových podmínek za běhu. Výsledky obou algoritmů (v~další kapitole) na tento fakt ukazují.


	\item Překročení časového limitu a přerovnání úloh: Prohledávací algoritmus se čas od času
	dostane do takové části stromu, která zdaleka nevede k~řešení a
	protože je strom velký, prohledával by velmi dlouho. Vložili jsme
	do celého prohledávání časové omezení na dobu hledání. Pokud
	nedojde k~nalezení řešení dřív, přistupuje se k~zvýšení časového
	limitu (tím pádem nehrozí zacyklení celého algoritmu) a k~přerovnání úloh při konstantní hodnotě minimálního
	času. Tato funkčnost znovu oživí hledání a ve většině případů dojde
k~řešení rychleji než bez přerovnání.
	\placeformula
	\startformula \startalign
	\NC \mbox{limit}(x)\NC= n \cdot m \cdot x + \mbox{limit}(x-1)\NR[eq:limit]
	\NC \mbox{limit}(0)\NC=n \cdot m\NR
	\stopalign \stopformula
		$x$ značí iteraci - kolikrát se dosáhlo časového limitu. $n$, $m$ je velikost matice T.
\stopitemize

%\input images/metapost/flowchart.tex
\placefigure[force,here][fig:flowchart]
	{Vývojový diagram algoritmu}
	{\externalfigure[images/flowchart]}

%\section{Spojení Gecode a Matlabu}
%Knihovna Gecode má v porovnání s ostatními podobnými systémy výhodu
%nejen v rychlosti, ale také v tom, že je napsaná v C++ a tím pádem není
%velký problém spojit ji s Matlabem. To se provádí přes standartní
%interface Matlabu.

\page
